package org.JavaAlgorithmManual;

/**
 * @Auther: qingle
 * @Date: 2024/10/6-9:21
 * @Description: Eight Queen Problem
 * n-queen problem
 * N皇后问题（n-queen problem）是一个经典的组合优化问题，也是一个使用回溯法（backtracking）的典型例子。
 * 回溯法是一种系统地搜索问题解的方法。
 *
 * 该方法在第n列的各行上依次试探，并判断是否形成攻击，如果没有冲突，则递归调用该方法来摆放下一个皇后。
 * 当所有皇后都放置后，便输出结果。
 * @version: 1.0
 */
public class N9_9_EightQueenProblem {

	static int iCount = 0; //全局变量,记录解的序号
	static int[] weiZhi = new int[8]; // 全局数组，记录皇后在各列上的放置位置

	void eightQueue(int n) {
		int ct;// ct 用于判断是否冲突
		if (n == 8) {
			Output(); // 输出求解的结果
			return;
		}

		for (int i = 0; i < 8; i++) { // 试探
			weiZhi[n] = i; // 在该列的第i行放置
			// 判断第n和皇后是否与前面的皇后形成攻击
			ct = 1;
			for (int j = 0; j < n; j++) {
				if (weiZhi[j] == weiZhi[i]) {
					ct = 0;
				}else if(Math.abs(weiZhi[i] - weiZhi[j]) == (n - j)){
					ct = 0;
				}else{
					//
				}

				if(ct == 1){
					eightQueue(n + 1);
				}
			}
		}
	}

	private void Output() {
		System.out.println();
	}


}
